#pragma once

#include <iostream>
using namespace std;

template <class K>
struct BSTNode
{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;

	BSTNode(const K& key = K())
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}

};

template <class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	bool Insert(const K& key)
	{
		// 如果为空树，则直接建立一个节点
		// 将其地址存放在_root上
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

		// 一直循环到cur为空
		while (cur) {
			if (key > cur->_key) {
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				// 如果中途发现BS树已有key，则插入失败
				// BS树中没有重复元素，依据定义
				return false;
			}
		}

		// 此时建立一个节点，将其地址赋值给cur
		cur = new Node(key);

		// 此时需要根据值的大小来判断parent左链还是右链
		if (key > parent->_key)
			parent->_right = cur;
		else parent->_left = cur;

		return true;
	}

	bool Find(const K& key)
	{
		Node* cur = _root;

		while (cur) {
			if (key > cur->_key) 
				cur = cur->_right;

			else if (key < cur->_key) 
				cur = cur->_left;

			else return true;
		}

		return false;
	}

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key) {
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				// 此时cur找到了节点
				// 该节点就是我们想要删除的节点

				// 如果左孩子为空
				// 这时候就要parent就要链到cur的右边去
				if (cur->_left == nullptr) {
					// 如果这个时候cur就是根
					// 那就_root移动一下
					if (parent == nullptr) {
						_root = _root->_right;

						delete cur;
						cur = nullptr;
						return true;
					}

					if (parent->_left == cur)
						parent->_left = cur->_right;
					else parent->_right = cur->_right;

					// 删除
					delete cur;
					cur = nullptr;

					return true;
				}

				// 如果右孩子为空
				// 这时候就要parent就要链到cur的左边去
				else if (cur->_right == nullptr) {
					// 如果这个时候cur就是根
					// 那就_root移动一下
					if (parent == nullptr) {
						_root = _root->_left;

						delete cur;
						cur = nullptr;
						return true;
					}

					if (parent->_left == cur)
						parent->_left = cur->_left;
					else parent->_right = cur->_left;

					// 删除
					delete cur;
					cur = nullptr;

					return true;
				}

				// 需要注意的是
				// 前面两种情况看似只包含了cur节点有一个孩子的情况
				// 其实也将cur节点没有孩子的情况处理了
				// 现在只要处理当cur节点有两个孩子的时候了
				// 这时候我们采用替换删除法
				// 找到右子树最小 或者 左子树最大都行
				// 因为要找的这个节点在不影响树形结构的前提下
				// 要做到大于所有cur左子树的，小于所有cur右子树的
				// 在这里，我们选择前者，即右子树最小的，也就是右子树最左侧的
				else {
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					
					// 找到右子树的最小节点
					while (rightMin->_left) {
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}

					// 替代，这时候转换成就要删除rightMin这个节点了
					// 这个时候就需要有它的父亲
					cur->_key = rightMin->_key;

					// 因为rightMin必然是最左节点
					// 所以rightMinP必然是链接rightMin的右孩子
					// 同时rightMinP是左链还是右链这不确定，需要判断一下
					if (rightMinP->_left == rightMin)
						rightMinP->_left = rightMin->_right;
					else rightMinP->_right = rightMin->_right;

					delete rightMin;
					rightMin = nullptr;

					return true;
				}
			}
		}

		return false;
	}


	// 中序遍历，因为外部无妨访问私有变量_root
	// 于是封装一下
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	// 函数名前面加_表示子函数
	void _InOrder(Node* _root)
	{
		if (_root == nullptr) {
			return;
		}

		_InOrder(_root->_left);
		cout << _root->_key << " ";
		_InOrder(_root->_right);
	}
private:
	Node* _root;
};